import java.util.HashMap;
import java.util.Map;

/**
 * 659. 分割数组为连续子序列
 * https://leetcode-cn.com/problems/split-array-into-consecutive-subsequences/
 */
public class Solutions_659 {
    public static void main(String[] args) {
//        int[] nums = {1, 2, 3, 3, 4, 5};  // output: true
//        int[] nums = {1, 2, 3, 3, 4, 4, 5, 5};  // output: true
        int[] nums = {1, 2, 3, 4, 4, 5};  // output: false

        boolean result = isPossible(nums);
        System.out.println(result);
    }

    /**
     * 解题思路：（贪心思想）
     * 将 nums 中的元素及其出现次数记录到 map 中
     *  - 当后面的元素出现次数大于等于当前元素的出现次数时，那么后面的元素就可以拼接到子序列中
     *  - 若是后面的元素出现次数小于当前元素的出现次数时，那么是无法满足条件的
     *  使用一次后，需要将 map 中的出现次数减 1
     */
    public static boolean isPossible(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        for (int num : nums) {
            // 子序列长度
            int subCount = 0;
            // 最少出现次数为 1，才能拼接到子序列中（temp 每次取当前元素的出现次数）
            int temp = 1;
            // 当前元素为 cur，那么 cur 的连续元素为 cur + 1
            int cur = num;
            // cur 出现次数大于等于 temp 时，可以拼接到连续的子序列中
            while (map.getOrDefault(cur, 0) >= temp) {
                // 当前元素的出现次数
                temp = map.getOrDefault(cur, 0);
                // 使用了 1 次，那么出现次数减 1
                map.put(cur, temp - 1);
                subCount ++;
                cur ++;
            }
            if (subCount > 0 && subCount < 3) {
                // 无法组成 3 个元素的子序列
                return false;
            }
        }
        return true;
    }
}